package LeetCode.NumOffer;

public class NumOffer12 {
    public static boolean exist(char[][] board, String word) {
        if(board.length == 0 && board[0].length == 0){
            return false;
        }
        char[] Word = word.toCharArray();
        if(Word.length == 0){
            return false;
        }
        if(Word.length > board.length * board[0].length){
            return false;
        }
        //二维数组的行
        int row = 0;
        //二维数组的列
        int col = 0;
        //英语单词字母的位置
        int i = 0;
        return find(board,Word,i,row,col);
    }
//    在二维数组中寻找字符串第一个字母的位置
    public static boolean find(char[][] board,char[] Word,int i,int row,int col){
        if(board[row][col] == Word[0]){
            return Exist(board,Word,0,row,col);
        }else{
            for (int m = 0; m < board.length; m++) {
                for (int n = 0; n < board[0].length; n++) {
                    if(board[m][n] == Word[0]){
                        return Exist(board,Word,0,m,n);
                    }
                }
            }
        }
        return false;
    }
    public static boolean Exist(char[][] board,char[] Word,int i,int row,int col){
        if(i == Word.length){
            return true;
        }
        if(row < 0 || col < 0 || row >= board.length || col >= board[0].length){
            return false;
        }
        if(board[row][col] == Word[i]){
            board[row][col] = ' ';
            i += 1;
            return Exist(board, Word, i, row + 1, col) || Exist(board, Word, i, row - 1, col)
                    || Exist(board, Word, i, row, col + 1) || Exist(board, Word, i, row, col - 1);
        }else{
//            board[row][col] = Word[i];
            return false;
        }
    }

    public static void main(String[] args) {
        char[][] board = {{'A','B'},
                          {'S','F'}};
        String word = "SFBA";
        System.out.println(exist(board,word));
    }
}
